#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "quadtree.h"
#include "lista.h"
#define  CAPACIDAD_NODO 4

struct punto{
	int x;
	int y;
};

typedef struct rec{
	punto_t* arr_izq; 
	punto_t* aba_der;
}rec_t;

struct quadtree{
	rec_t* area;
	lista_t* lista_puntos;
	quadtree_t* noroeste;
	quadtree_t* noreste;
	quadtree_t* suroeste;
	quadtree_t* sureste;
};

typedef struct _sucursal{
	punto_t* coordenadas;
	char *nombre;
}sucursal_t;



// Se crea el arbol vacio
// se debe pasar cmo parametro los puntos que forman el
// area del quadtree a crear. 
quadtree_t* quadtree_crear(int x_arr,int y_arr, int x_aba, int y_aba){
	quadtree_t* arbol = malloc(sizeof(quadtree_t));
	if (!arbol) return NULL;
	
	arbol->area = malloc(sizeof(rec_t));
	if(!arbol->area){ 
		free(arbol);		
		return NULL;
	}

	arbol->area->arr_izq = malloc(sizeof(punto_t));
	if(!arbol->area->arr_izq){
		free(arbol->area);
		free(arbol);
		return NULL;
	}

	arbol->area->aba_der = malloc(sizeof(punto_t));
	if(!arbol->area->aba_der){
		free(arbol->area->arr_izq);
		free(arbol->area);
		free(arbol);
		return NULL;
	}

	arbol->area->arr_izq->x = x_arr ;
	arbol->area->arr_izq->y = y_arr ;	
	arbol->area->aba_der->x = x_aba ;
	arbol->area->aba_der->y = y_aba ;


	arbol->lista_puntos = lista_crear();
	arbol->noroeste = NULL;
	arbol->noreste = NULL;	
	arbol->suroeste = NULL;
	arbol->sureste = NULL;


	return arbol;



}

// Informa si el punto se encuentra dentro del rectangulo
// puseto como parametro.
bool contiene_punto(rec_t* rectangulo,punto_t* punto ){

	
	if(punto->x > rectangulo->arr_izq->x){
		if(punto->x < rectangulo->aba_der->x){
			if(punto->y > rectangulo->aba_der->y){
				if(punto->y < rectangulo->arr_izq->y) return true;
			}
		}
	}

	return false;
				

}

// Parte en cuatro al quadtree que introducimos por parametro.
bool subdividir_quadtree(quadtree_t* quadt){

	if(quadt->noroeste) return true;

	int x_medio = ((quadt->area->aba_der->x + quadt->area->arr_izq->x) /2);
	int y_medio = ((quadt->area->arr_izq->y + quadt->area->aba_der->y) /2);

	
	quadt->noroeste = quadtree_crear(quadt->area->arr_izq->x,quadt->area->arr_izq->y,x_medio,y_medio);
	
	quadt->noreste = quadtree_crear(x_medio,quadt->area->arr_izq->y,quadt->area->aba_der->x,y_medio);

	quadt->suroeste = quadtree_crear(quadt->area->arr_izq->x,y_medio,x_medio,quadt->area->aba_der->y);

	quadt->sureste = quadtree_crear(x_medio,y_medio,quadt->area->aba_der->x,quadt->area->aba_der->y);


	return true;


}


// Se guarda un dato en el arbol.
// Pre: el arbol fue creado.
// Post: el arbol contiene un elemento mas si devuelve true,
// sino devuelve false.
bool quadtree_guardar(quadtree_t* quadt, void* dato){

	sucursal_t* sucursal = dato;
	int tope = lista_largo(quadt->lista_puntos);

	if(!contiene_punto(quadt->area,sucursal->coordenadas)) return false;

	if( tope < CAPACIDAD_NODO) {
		lista_insertar_ultimo(quadt->lista_puntos, sucursal);
		sucursal = lista_ver_primero(quadt->lista_puntos);
		tope++;
		return true;
	}
	else subdividir_quadtree(quadt);

	if(quadtree_guardar(quadt->noroeste,dato)) return true;
	if(quadtree_guardar(quadt->noreste,dato)) return true;
	if(quadtree_guardar(quadt->suroeste,dato)) return true;
	if(quadtree_guardar(quadt->sureste,dato)) return true;


	return false;


}

void _sucursal_destruir(void *dato){
	sucursal_t* sucursal = dato;
	free(sucursal->nombre);
	free(sucursal->coordenadas);
	free(sucursal);
}

// Destruyo el arbol por completo.
// Pre: el arbol fue creado.
// Post: se libera la memoria usada para generar al arbol.
void quadtree_destruir(quadtree_t* quadt){
	
	
	if(quadt->noroeste){
		quadtree_destruir(quadt->sureste);
		quadtree_destruir(quadt->suroeste);
		quadtree_destruir(quadt->noreste);
		quadtree_destruir(quadt->noroeste);
	}

	free(quadt->area->aba_der);
	free(quadt->area->arr_izq);	
	free(quadt->area);
	lista_destruir(quadt->lista_puntos,_sucursal_destruir);
	
	
	free(quadt);
}



// Agrega de la lista_2 a la lista 1 todo su contenido.
void agregar_a_lista(lista_t* lista_1 ,lista_t* lista_2){

	lista_iter_t* iter = lista_iter_crear(lista_2);
	sucursal_t* sucursal;

	while(!lista_iter_al_final(iter)){
		sucursal = lista_iter_ver_actual(iter);
		lista_insertar_ultimo(lista_1,sucursal);
		lista_iter_avanzar(iter);
	}

	lista_iter_destruir(iter);
	lista_destruir(lista_2,NULL);
	
}

// Informa si hay corte entre los dos rectangulos informados.
bool intersectan(rec_t* rect_1 ,rec_t* rect_2){

	punto_t* punto = malloc(sizeof(punto_t));
	if(!punto) return false;

	if(contiene_punto(rect_1,rect_2->arr_izq)){
		free(punto);	
		return true;
	}

	if(contiene_punto(rect_1,rect_2->aba_der)){
		free(punto);		
		return true;
	}

	punto->x = rect_2->arr_izq->x ;
	punto->y = rect_2->aba_der->y ;

	if(contiene_punto(rect_1,punto)){ 
		free(punto);		
		return true;
	}

	punto->x = rect_2->aba_der->x ;
	punto->y = rect_2->arr_izq->y ;


	if(contiene_punto(rect_1,punto)){
		free(punto);		
		return true;
	}

	free(punto);
	return false;	
}



/**/
rec_t* crear_cuadrante(punto_t* punto){

	rec_t* cuadrante = malloc(sizeof(rec_t));
	if(!cuadrante) return NULL;

	cuadrante->arr_izq = malloc(sizeof(punto_t));
	if(!cuadrante->arr_izq){
		free(cuadrante);		
		return NULL;
	}
	
	cuadrante->aba_der = malloc(sizeof(punto_t));
	if(!cuadrante->aba_der){
		free(cuadrante->arr_izq);		
		free(cuadrante);
		return NULL;
	}

	cuadrante->arr_izq->x = (punto->x)-1000;
	cuadrante->arr_izq->y = (punto->y)+1000;
	cuadrante->aba_der->x = (punto->x)+1000;
	cuadrante->aba_der->y =	(punto->y)-1000;

	return cuadrante;

}

// Informa los puntos dentro del rectangulo.
// Pre: el arbol fue creado.
// Post: devuelve una lista con los puntos dentro del rectanguo.
lista_t* quadtree_lista_puntos(quadtree_t* quadt , punto_t* punto){

	lista_t* lista = lista_crear();
	rec_t* rectangulo = crear_cuadrante(punto);

	if(!intersectan(quadt->area,rectangulo)){
		free(rectangulo->arr_izq);
		free(rectangulo->aba_der);
		free(rectangulo);	
		return lista;
	}

	sucursal_t* sucursal;
	lista_iter_t* iter = lista_iter_crear(quadt->lista_puntos);


	while(!lista_iter_al_final(iter)){
		sucursal = lista_iter_ver_actual(iter);
		if(contiene_punto(rectangulo,sucursal->coordenadas)) lista_insertar_ultimo(lista,sucursal);
		lista_iter_avanzar(iter);		
	}

	lista_iter_destruir(iter);

	free(rectangulo->arr_izq);
	free(rectangulo->aba_der);
	free(rectangulo);

	if(quadt->noroeste == NULL) return lista;

	agregar_a_lista(lista,quadtree_lista_puntos(quadt->noroeste,punto));
	agregar_a_lista(lista,quadtree_lista_puntos(quadt->noreste,punto));	
	agregar_a_lista(lista,quadtree_lista_puntos(quadt->suroeste,punto));
	agregar_a_lista(lista,quadtree_lista_puntos(quadt->sureste,punto));
	

	return lista;

}

// Informa si la sucursal pertenece al arbol.
// Pre: se creo el arbol.
// Post: devuelve true si pertenece y de lo contrario false.
bool pertenece_sucursal(quadtree_t* quadt , char* nombre){

	lista_iter_t* iter = lista_iter_crear(quadt->lista_puntos);
	sucursal_t* sucursal;

	while( !lista_iter_al_final(iter) ){
		sucursal = lista_iter_ver_actual(iter);
		if( strcmp(sucursal->nombre,nombre) == 0 ) return true;
		lista_iter_avanzar(iter);
	}

	if( !quadt->noroeste ) return false;
	
	if( pertenece_sucursal( quadt->noroeste ,nombre ) ) return true;
	if( pertenece_sucursal( quadt->noreste ,nombre ) ) return true;
	if( pertenece_sucursal( quadt->suroeste ,nombre ) ) return true;
	if( pertenece_sucursal( quadt->sureste ,nombre ) ) return true;

	return false;

		

}




